/* 
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).
 */

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        int slen = S.length();
        int sublen = L[0].length();
        multimap<string, int> mymap;
        vector<int> results;
        if (!slen || !sublen) {
            return results;
        }
        // add substrings to map and clear values
        for (int i=0; i<L.size(); i++) {
            mymap.insert(pair<string, int>(L[i], 0));
        }
        for (int j = 0; j <= slen-sublen; j++) {
            int sj, found_total;
            multimap<string, int>::iterator it;
            // set values back to 0
            for (it = mymap.begin(); it != mymap.end(); it++) {
                it->second = 0;
            }
            for (sj = j, found_total = 0;
                 sj <= slen-sublen && found_total < L.size();
                 sj += sublen, found_total++) {
                int found_one = 0;
                pair<multimap<string,int>::iterator,multimap<string,int>::iterator> ret = \
                    mymap.equal_range(string(S, sj, sublen));
                for (it = ret.first; it != ret.second; it++) {
                    if (it->second == 0) {
                        // found one set flag and proceed
                        it->second = 1;
                        found_one = 1;
                        break;
                    }
                }
                if (!found_one) { break;}
            }
            if (found_total == L.size()) {
                results.push_back(j);
            }
        }
    }
};
